package 极客算法训练营.chapter08;


import java.util.*;

public class 多数元素 {

    class Solution1 {
        public int majorityElement(int[] nums) {
            int len = nums.length / 2;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
            Set<Integer> number = map.keySet();
            Optional<Integer> first = number.stream().filter(e -> map.get(e) > len).findFirst();
            return first.get();
        }
    }

    class Solution2 {
        public int majorityElement(int[] nums) {
            Integer ans = null;
            int len = nums.length / 2;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
            Set<Integer> number = map.keySet();
            for (Integer num : number) {
                if (map.get(num) > len) {
                    ans = num;
                }
            }
            return ans;
        }
    }

    class Solution3 {
        public int majorityElement(int[] nums) {
            int len = nums.length / 2;
            //边界判断：如果只有一个元素，直接返回
            if (len == 0) return nums[0];
            int count = 1;
            Integer ans = null;
            Arrays.sort(nums);
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == nums[i - 1]){
                    if (++count > len) {
                        ans = nums[i];
                        break;
                    }
                } else {
                    count = 1;
                }
            }
            return ans;
        }
    }
    class Solution4 {
        public int majorityElement(int[] nums) {
            return dfs(nums, 0, nums.length - 1);
        }

        private int dfs(int[] nums, int start, int end) {
            //terminator
            if (start == end) {
                return nums[start];
            }
            int mid = start + (end - start) / 2;
            //case A
            int left = dfs(nums, start, mid);
            //case B
            int right = dfs(nums, mid + 1, end);
            //generate result
            int left_count = numCount(nums, left, start, mid);
            int right_count = numCount(nums, right, mid + 1, end);
            return left_count > right_count ? left : right;
        }

        public int numCount(int[] nums, int num, int start, int end) {
            int count = 0;
            for (int i = start; i <= end; i++) {
                if (nums[i] == num) count++;
            }
            return count;
        }
    }
}
